package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder3

/**
 * https://leetcode.cn/problems/delete-nodes-and-return-forest/description
 *
 * 题型： 二叉树的后序遍历 + 分治法
 *
 * ```
 * 1110. 删点成林
 * 给出二叉树的根节点 root，树上每个节点都有一个不同的值。
 * 如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。
 * 返回森林中的每棵树。你可以按任意顺序组织答案。
 *
 * 示例 1：
 * 输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
 * 输出：[[1,2,null,4],[6],[7]]
 *
 * 示例 2：
 * 输入：root = [1,2,4,null,3], to_delete = [3]
 * 输出：[[1,2,4]]
 *
 * 提示：
 * 树中的节点数最大为 1000。
 * 每个节点都有一个介于 1 到 1000 之间的值，且各不相同。
 * to_delete.length <= 1000
 * to_delete 包含一些从 1 到 1000、各不相同的值。
 * ```
 */
class leetcode_1110 {
    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val root = n1
        n1.left = n2
        n1.right = n4
        n4.right = n3

        val actual = delNodes(root, intArrayOf(3))
        val expected = arrayListOf(1, 2, 4)
        Assert.assertEquals(1, actual.size)
        Assert.assertEquals(expected.toString(), printLevelOrder3(actual[0]).toString())
    }

    private fun delNodes(root: TreeNode?, to_delete: IntArray): List<TreeNode?> {
        /**
        题型： 二叉树的后序遍历 + 分治法

        思路：
        新左子树=递归后的左子树
        新右子树=递归后的右子树
        当前节点被删除，若新左/右子树不为空，则加入结果集，并返回null
        当前节点不被删除，返回当前节点
         */
        val result: ArrayList<TreeNode?> = ArrayList()

        val temp = delete(root, to_delete, result)
        if (temp != null) {
            // 没有节点被删除，则加入结果集
            result.add(temp)
        }

        return result
    }

    private fun delete(root: TreeNode?, to_delete: IntArray, result: ArrayList<TreeNode?>): TreeNode? {
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if (null == root) {
            return null
        }

        // 3 确定当层递归的处理逻辑: 后序遍历
        // 左
        root.left = delete(root.left, to_delete, result)

        // 右
        root.right = delete(root.right, to_delete, result)

        // 中
        if (to_delete.contains(root.`val`)) { // 当前节点是否被删除，
            // 当前节点被删除，若左/右子树不为空，则加入结果集，并返回null
            if (root.left != null) {
                result.add(root.left)
            }
            if (root.right != null) {
                result.add(root.right)
            }
            return null
        }
        return root
    }
}